#pragma once
/***
 *  线性表 c语言实现（顺序表）
 *
 */

/***
 * 抽象数据类型线性表定义
 * ADT List{
 * 数据对象：D
 * 数据关系：R1
 * 基本操作：
 * InitList(&L)
 *  操作结果：构造一个空的线性表L
 * ClearList(&L)
 *  初始条件：线性表L已存在
 *  操作结果：将L重置为空表
 * ListEmpty(L)
 *  初始条件：线性表L已存在
 *  操作结果：若L为空表，则返回TRUE，否则返回false
 * ListLength(L)
 *  初始条件：线性表L已存在
 *  操作结果：返回L中的数据元素个数
 * GetElem(L,i,&e)
 *  初始条件：线性表L已存在
 *  操作结果：用e返回L中第i个元素
 * LocateElem(L,e，compare())
 *  初始条件：线性表L已存在
 *  操作结果：返回L中第一个与e满足关系compare()的数据元素的位序
 * PriorElem(L,cur_e,&pre_e)
 *  初始条件：线性表L已存在
 *  操作结果：返回L中第一个与e相等的前一个元素
 * NextElem(L,cur_e,&next_e)
 *  初始条件：线性表L已存在
 *  操作结果：返回L中第一个与e相等的后一个元素
 * ListInsert(L,i,e)
 *  初始条件：线性表L已存在
 *  操作结果：插入元素e，在第i个位置
 * ListDelete(L,i,e)
 *  初始条件：线性表L已存在
 *  操作结果：删除在第i个位置元素，并用e返回
 * ListTraverse(L,visit())
 * 初始条件：线性表L已存在
 * 操作结果: 依次对L的每个数据元素调用函数visit(),一旦调用visit()失败，则操作失败
 */

// c语言函数学习，
// memcpy，内存拷贝
// memmove,内存移动
// memcmp,内存比较
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#define ElemType unsigned char
#define INIT_SIZE 10
typedef struct
{
    ElemType *elem; // 存放元素
    int size;       // 存放元素字节大小
    int length;     // 当前表长度
    int listSize;   // 当前表容量大小
} SqList;
// c 语言不能直接传引用
void InitList(SqList *list, int size)
{
    list->elem = 0;
    list->length = 0;
    list->listSize = 0;
    list->size = size;
};

void ClearList(SqList *list)
{
    free(list->elem);
    list->length = 0;
    list->listSize = 0;
    list->size = 0;
};

bool ListEmpty(SqList *list)
{
    return list->length == 0;
};

int ListLength(SqList *list)
{
    return list->length;
};

void inflate(SqList *list, int increase)
{
    int newlistSize = list->listSize + increase;
    int newBytes = newlistSize * list->size;
    int oldBytes = list->listSize * list->size;
    // 分配新内存（C语言使用malloc）
    unsigned char *b = (unsigned char *)malloc(newBytes);
    if (b == NULL)
    {
        // 内存分配失败处理
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }

    // 复制旧数据（使用memcpy替代循环）
    memcpy(b, list->elem, oldBytes);
    free(list->elem);
    list->elem = b;
    list->listSize = newlistSize;
};

void *GetElem(SqList *list, int index)
{
    assert(0 <= index);
    if (index >= list->length)
    {
        return 0;
    }
    return &(list->elem[index * list->size]); // 2.返回元素起始地址
};

int LocateElem(SqList *list, void *e)
{
    if (list == NULL || e == NULL || list->length == 0)
        return -1; // 无效输入或空表处理

    for (int i = 0; i < list->length; i++)
    {
        // 计算当前元素的内存起始地址
        unsigned char *curElem = &(list->elem[i * list->size]);

        // 逐字节比较内存内容
        if (memcmp(curElem, e, list->size) == 0)
        {
            return i; // 找到匹配，返回索引位置
        }
    }
    return -1; // 未找到
};

int ListInsert(SqList *list, int i, const void *element)
{
    if (list == NULL || element == NULL)
        return -1;
    if (i < 0 || i > list->length)
        return -1;
    if (list->length >= list->listSize)
        inflate(list, INIT_SIZE);

    // 移动i之后的元素（内存级后移）
    if (i < list->length)
    {
        unsigned char *src = list->elem + i * list->size; // 源起始地址
        unsigned char *dest = src + list->size;           // 目标起始地址
        int moveBytes = (list->length - i) * list->size;  // 需移动的字节数
        memmove(dest, src, moveBytes);                    // 内存重叠安全移动
    }

    // 插入新元素到位置i
    unsigned char *target = list->elem + i * list->size;
    memcpy(target, element, list->size); // 内存复制元素内容
    list->length++;
    return i; // 返回插入位置
}

/**
 * 删除顺序表中位序i的元素并返回其指针
 * @param list 顺序表指针
 * @param i 要删除的位序 (0 ≤ i < length)
 * @return 成功返回被删除元素的指针（需调用者释放），失败返回NULL
 */
void *ListDelete(SqList *list, int i)
{
    // 参数校验
    if (list == NULL || i < 0 || i >= list->length)
        return NULL;

    // 动态分配内存存储被删除元素，使用完需要主动释放内存
    void *deletedElement = malloc(list->size);
    if (deletedElement == NULL)
    {
        return NULL; // 内存分配失败
    }

    // 计算目标元素地址并复制数据
    unsigned char *target = list->elem + i * list->size;
    memcpy(deletedElement, target, list->size);

    // 移动后续元素（内存级前移）
    if (i < list->length - 1)
    {
        unsigned char *src = target + list->size;
        size_t moveBytes = (list->length - i - 1) * list->size;
        memmove(target, src, moveBytes);
    }

    list->length--; // 更新长度
    return deletedElement;
};

void ListTraverse(SqList *list)
{
    for (int i = 0; i < list->length; i++)
    {
        if (list->size == 4)
        {
            //(int *)是强转unsigned char类型 为 int类型，因为里面内存数据存的是内存地址，所以需要*来解引用，所以组合起来是*(int *)
            printf("%d\n", *(int *)(list->elem + i * list->size));
        }
    }
};
